package mo.offer_special;

import java.util.ArrayDeque;
import java.util.Deque;

@SuppressWarnings("ConstantConditions")
public class L040 {

    public int maximalRectangle(String[] matrix) {
        int n = matrix.length;
        if(n == 0) {
            return 0;
        }
        int m = matrix[0].length();
        // 求每一行连续 1 的个数
        int[][] left = new int[n][m];
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                if(matrix[i].charAt(j) == '1') {
                    if(j == 0) {
                        left[i][j] = 1;
                    } else {
                        left[i][j] = left[i][j - 1] + 1;
                    }
                }
            }
        }

        int ans = 0;
        // 针对每一列，将每一列当作矩阵右边的边，求柱状图包含的最大矩形
        for(int i = 0; i < m; ++i) {
            Deque<Integer> stack = new ArrayDeque<>();
            stack.push(-1);
            for(int j = 0; j < n; ++j) {
                while(stack.peek() != -1 && left[stack.peek()][i] >= left[j][i]) {
                    int top = stack.pop();
                    ans = Math.max(ans, (j - stack.peek() - 1) * left[top][i]);
                }
                stack.push(j);
            }
            // 要注意如果栈中还剩元素，说明后面的柱子全部单调递增，那么所有递增的柱子右边界都是 n
            while(stack.peek() != -1) {
                int top = stack.pop();
                ans = Math.max(ans, (n - stack.peek() - 1) * left[top][i]);
            }
        }
        return ans;
    }

}
